2021年4月上海月赛甲组方格取数

2022-12-23 12:17| 来源: 网络整理| 查看: 265

文章目录方格路径题目描述输入格式输出格式数据范围样例数据输入:输出:输入:输出: 递推解法一：递推算法的时间复杂度解题思路二：数学解：当没有障碍物的时候：当存在k个障碍物的时：算法时间复杂度

方格路径

内存限制: 256 Mb

时间限制: 1000 ms

题目描述

在一个由 n×m个方格构成的图中，有 k 个方格是禁止进入的。请计算从左上角 (1,1)(1,1) 出发，每步朝右方或下方移动，不经过禁入的方格，最后到达右下角 (n,m) 的路径条数。由于答案很大，输出模 1,000,000,007 的余数。

输入格式

第一行：三个正整数表示n，m与 k。第二行到第 n+1行：第 i+1行表示一个禁入方格的坐标 ( x i , y i ) (x_i,y_i) (xi,yi)。保证 ( x i , y i ) (x_i,y_i) (xi,yi) 不会等于 (1,1) 或 (n,m)，也不会有一个坐标重复出现两次。

输出格式

单个自然数：表示路径数模 1,000,000,007 的余数。

数据范围对于 30% 的数据， 0 ≤ k ≤ 200 0\leq k\leq 200 0≤k≤200对于60% 的数据， 0 ≤ k ≤ 1500 0\leq k\leq 1500 0≤k≤1500对于 100% 的数据， 0 ≤ k ≤ 3000 0\leq k\leq 3000 0≤k≤3000 1 ≤ n , m ≤ 1 0 5 1\leq n,m\leq 10^5 1≤n,m≤105。样例数据输入: 100000 100000 4 50001 50001 50000 50000 50000 50001 50001 50000 输出: 999612315 输入: 2 2 2 2 1 1 2 输出: 0 递推解法一：递推

初看本题很像leecode 中63题。不同路径 ,我们也可以使用Leecode中递推解法。可以得到30分。主要是本题得N和M的取值范围是100000.

算法的时间复杂度

O ( N × M ) O(N\times M) O(N×M) .

#include #include #include #include using namespace std; typedef long long LL; inline int read() { int x = 0, f = 1; char s = getchar(); while (s '9') { if (s == '-') f = -f; s = getchar(); } while (s >= '0' && s public: int uniquePathsWithObstacles(vector &o) { int n = o.size(); if (n == 0) return 0; int m = o[0].size(); vector f(n, vector(m)); for (int i = 0; i if (!i && !j) f[i][j] = 1; else { if (i) f[i][j] += f[i - 1][j]; if (j) f[i][j] += f[i][j - 1]; } } } return f[n - 1][m - 1]; } }; int main() { int n = read(), m = read(), k = read(); vector o(n, vector(m, 0)); for (int i = 1; i LL x = 0, f = 1; char s = getchar(); while (s '9') { if (s == '-') f = -f; s = getchar(); } while (s >= '0' && s LL res = 1; while (b) { if (b & 1) res = res * a % P; a = a * a % P; b >>= 1; } return res; } void init() // 初始化数组f[N] 和 g[N] { f[0] = g[0] = 1; for (LL i = 1; i return (f[n] * g[n - m]) % P * g[m] % P; } int main() { LL n = read(), m = read(); init(); cout if (a.x != b.x) return a.x if (s == '-') f = -f; s = getchar(); } while (s >= '0' && s LL res = 1; while (b) { if (b & 1) res = res * a % P; a = a * a % P; b >>= 1; } return res; } void init() { f[0] = g[0] = 1; for (LL i = 1; i return (f[n] * g[n - m]) % P * g[m] % P; } int main() { // 读入数据 LL n = read(), m = read(), k = read(); for (int i = 1; i ans[i] = getC(pos[i].x + pos[i].y - 2, pos[i].x - 1); for (int j = 1; j

【本文地址】

公司简介

联系我们

2021年4月 上海月赛甲组 方格取数

2021年4月上海月赛甲组方格取数